package com.mlh.binarysearch;

/**
 * @author 缪林辉
 * @date 2024/8/29 21:15
 * @DESCRIPTION
 */
//给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]。
// 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
public class 在排序数组中查找元素的第一个和最后一个位置 {
    //通过两次二分查找，第一次查找到第一个等于target的位置
    //第二次查找到最后一个等于target的位置
    public int[] method1(int[] nums, int target) {
        int firstIndex=-1,lastIndex=-1;
        int left=0,right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                firstIndex=mid;
                right=mid-1;//查找到第一个等于target的位置的关键代码
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        left=0;
        right=nums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                lastIndex=mid;
                left=mid+1;//查找到最后一个等于target的位置的关键代码
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return new int[]{firstIndex,lastIndex};
    }
}
